#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using u64 = unsigned long long;
using i128 = __int128;

//柏长盛
#include <bits/stdc++.h>
using ll = long long;
using u64 = unsigned long long;
using i128 = __int128;

struct I128Utils {
    // 自定义 abs 函数以支持 i128
    static i128 abs(i128 x) {
        return x < 0 ? -x : x;
    }

    // 将 i128 转换为字符串
    static std::string to_string(i128 n) {
        if (n == 0) return "0";
        bool neg = n < 0;
        if (neg) n = -n;

        std::string res;
        while (n > 0) {
            res += char('0' + n % 10);
            n /= 10;
        }

        if (neg) res += '-';
        std::reverse(res.begin(), res.end());
        return res;
    }

    // 从字符串解析为 i128
    static i128 from_string(const std::string& s) {
        i128 n = 0;
        size_t i = 0;
        bool neg = false;
        if (s[0] == '-') {
            neg = true;
            i = 1;
        }
        for (; i < s.size(); ++i) {
            n = n * 10 + (s[i] - '0');
        }
        return neg ? -n : n;
    }

    // 计算整数平方根（向下取整），负数抛异常
    static i128 sqrt(i128 n) {
        if (n < 0) return -1;
        i128 lo = 0, hi = 1e18;
        while (lo < hi) {
            i128 mid = (lo + hi + 1) / 2;
            if (mid * mid <= n) {
                lo = mid;
            } else {
                hi = mid - 1;
            }
        }
        return lo;
    }

    // 计算 GCD
    static i128 gcd(i128 a, i128 b) {
        a = abs(a);
        b = abs(b);
        while (b) {
            a %= b;
            std::swap(a, b);
        }
        return a;
    }

    // 计算 LCM
    static i128 lcm(i128 a, i128 b) {
        if (a == 0 || b == 0) return 0;
        return abs(a / gcd(a, b) * b);
    }

    // 幂（不支持负指数）
    static i128 pow(i128 base, i128 exp) {
        if (exp < 0) {
            return -1;
        }
        i128 res = 1;
        while (exp > 0) {
            if (exp % 2 == 1) res *= base;
            base *= base;
            exp /= 2;
        }
        return res;
    }

    // 试除法判断素数（适合较小范围）
    static bool is_prime(i128 n) {
        if (n < 2) return false;
        if (n == 2 || n == 3) return true;
        if (n % 2 == 0 || n % 3 == 0) return false;
        for (i128 i = 5; i * i <= n; i += 6) {
            if (n % i == 0 || n % (i + 2) == 0) return false;
        }
        return true;
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);



    return 0;
}

//我的模板
__int128 read(string& s)
{
    __int128 res = 0;
    for (char c : s) res = res * 10 + c - '0';
    return res;
}

inline __int128 read()
{
    __int128 x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch>'9') {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
        x = x * 10 + ch - '0', ch = getchar();
    return x * f;
}

void print(__int128 x)
{
    if (x == 0) { cout << 0;return; }
    if (x < 0) { cout << '-';print(-x); return; }
    vector<int> res;
    while (x) {
        res.push_back(x % 10);
        x = x / 10;
    }
    reverse(res.begin(), res.end());
    for (int it : res) cout << it;
}